1. Field of the Invention
The present invention generally relates to a computer-implemented method for clustering retail sales data, and more particularly to a method which assumes a model of retail demand as a function, for example, of the price, base sales rate, and seasonal factors, and clusters together items that have, for example, the same seasonal and price effect factors based on the model fit.
2. Description of the Related Art
Conventional systems utilize clustering for the construction of a classification scheme over a set of objects such that objects within classes are similar in some respects but are different from those in other classes.
The basic data for cluster analysis is a set of N entities for each of which p attribute values have been observed (e.g., N retail items for each of which the last 52 weeks of sales has been observed). The major features of cluster analysis include:
Choice of variablesxe2x80x94This feature deals with determining which attributes of the elements to be clustered will be considered.
Measurement of similarity or distancexe2x80x94Most clustering techniques begin with a calculation of a matrix of similarities or distances between the entities to determine their xe2x80x9cclosenessxe2x80x9d for clustering. Additionally, a measure of similarity should be definable between groups. Some typical choices are Euclidean distance, city block distance, Minkowski distance, and similarity coefficients based on the Pearson or Spearman correlation coefficients, as discussed for example in Kaufman et al., xe2x80x9cFinding Groups in Data-An Introduction to Cluster Analysisxe2x80x9d, John Wiley and Sons, 1990.
Generation of clustersxe2x80x94All clustering techniques attempt to partition the data set into a set of clusters such that individuals in a cluster have high similarity to one another and differ from those in other clusters. Similarity is defined quantitatively as discussed above. A number of techniques exist for clustering and differ in the approaches used for initiating clusters, searching through the solution space for target clusters, and the termination criterion. Some known clustering techniques relevant to the present invention include:
Hierarchical clustering: Given n objects, hierarchical clustering consists of a series of clustering from the initial situation when each object may be considered a singleton cluster to the other extreme where all objects belong to one cluster. Hierarchical techniques may be subdivided into agglomerative methods which proceed by a series of successive fusions of the n objects into groups, and divisive methods which partition the set of n entities successively into finer partitions.
Optimization techniques: Optimization techniques attempt to form an optimal k-partition over the given set of objects (i.e., divide the set of entities into k mutually exclusive clusters) to optimize a pre-defined objective function, where k is usually input by the user. The pre-defined objective function is usually a measure for maximizing similarity within the cluster and the distance between clusters. The techniques employed differ in the methods by which an initial partition of the data is obtained, and the method for iteratively searching for the optimal partition.
Other techniques include density search, fuzzy clustering, neural networks, and conceptual clustering, as described, for example, in B. Everitt, xe2x80x9cCluster Analysisxe2x80x9d, Third Edition, Edward Arnold, 1993.
The term model-based clustering has also been used in another context, as described in Banfield et al., xe2x80x9cModel-Based Gaussian and Non-Gaussian Clusteringxe2x80x9d, Biometrics, 49, 803-822, 1993. This approach assumes a probability model for the population of interest and a density function for the observations.
In practical applications, among the popular methods for clustering are hierarchical- and optimization-based techniques, as mentioned above, which can be used to cluster retail sales data based on differences in the time series. Other applications of clustering can be found in a range of areas from finance (e.g., clustering stock price movement data) to the social sciences (e.g., clustering data on people""s responses and preferences).
However, currently available methods for clustering do not assume a model relating the independent and dependent variables, and are hence, for example, in a retail environment, restricted to grouping only on the basis of observed sales data. Therefore, separating items on the basis of price effects etc. on demand is impossible.
For example, consider the sales of two items (e.g., sales1 and sales2) shown in FIG. 5A. Looking only at the sales data, they appear similar in sales pattern over time (e.g., weeks, months, etc.), and as such, the items would be assumed to exhibit similar seasonal behavior. However, when other factors are also considered (e.g., such as price in FIG. 5B), and a model relating the sales to the price is assumed, then differing seasonal patterns and differing price sensitivities may be shown (e.g., see FIG. 5C). The conventional techniques do not provide for such consideration of other such variables. Instead, the conventional techniques factor only one variable.
Thus, conventional clustering techniques use only one stream of data (e.g., such as the sales data over time) and have no capability for factoring other data streams/variables, and thus may erroneously classify (e.g., cluster) items 1 and 2 as similar, when in fact the items are not similar.
In view of the foregoing and other problems of the conventional methods and techniques, an object of the present invention is to provide a method for grouping of data sets (e.g., not restricted to retail sales data, but described below simply as an example) in cases where the data set includes an observed or dependent value, and one or more controllable or independent values, based on a model relating the independent and dependent variables.
In a first aspect, a method of grouping multiple data points, each data point being a set (e.g., a vector, a xe2x80x9ctuplexe2x80x9d, etc.) comprising a measured dependent value and at least one related independent variable value, includes fitting the data into a model relating the independent and dependent variables of the data, and calculating a similarity and a distance between the data points and groups of the data points, thereby to group the multiple data points.
In a second aspect, a system for grouping multiple data points, each data point being a set (e.g., a vector, a xe2x80x9ctuplexe2x80x9d, etc.) comprising a measured dependent value and at least one related independent variable value, includes means for fitting the data into a model relating the independent and dependent variables of the data, and means for calculating similarity and distance between the data points and groups of the data points, thereby to group the multiple data points.
In a third aspect, a signal-bearing medium is provided tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for computer-implemented model-based clustering for grouping multiple data points, each data point being a set (e.g., a vector, a xe2x80x9ctuplexe2x80x9d, etc.) comprising a measured dependent value and at least one related independent variable value, the program including fitting the data into a model relating the independent and dependent variables of the data, and calculating similarity and distance between the data points and groups of the data points, thereby to group the multiple data points.
In a fourth aspect, a method of model-based clustering, includes initializing clustering parameters for a plurality of items; reading-in an actual data set used for clustering, and reading cluster center seeds, and calculating an target number of clusters; incrementing an iteration counter; scoring each item in the data set against all the available cluster centers using a similarity measure process, wherein if a similarity measure value of the item being examined is greater than a minimum first parameter, no further search is performed for the item, and the item is assigned to a particular cluster, and when the similarity measure value is less than said minimum first parameter, the item is assigned to the cluster against which the item scores the highest; removing clusters having a predetermined low number of assigned items, the removed clusters including items which are unassigned; updating cluster centers for all the remaining clusters; calculating an overall average cluster score as the average of all the average cluster scores to determine an overall distance, an overall distance being recorded for each iteration performed; determining whether the iteration is an odd-numbered iteration, wherein if it is determined that the iteration is an odd numbered iteration and that the remaining number of clusters is less than twice the target number calculated, then for each cluster checking a splitting criterion; determining whether a cluster is a candidate for splitting based on whether 100xe2x88x92average cluster score greater than overall distance, and the cluster has more than twice the minimum number of items needed, wherein an item which scores the least by having a lowest similarity measure against the cluster center is used as a seed for a new cluster that is formed; and assigning all items to clusters using the similarity measure calculation.
The method according to the fourth aspect further includes determining whether the iteration is an even-numbered iteration, wherein for even-numbered iterations, joining of clusters is attempted, and each cluster is scored against the other using a process of finding the similarity between two clusters, and for each cluster a most similar cluster is found; checking the similarity measure against a parameter MINCOMBINE, wherein if the similarity score is higher, then that pair of clusters are combined into one cluster by using any one of the centers, and destroying the other cluster; assigning all items to clusters based on said similarity measure; checking the iteration number against a maximum iteration parameter, wherein if the iteration number is less than said maximum iteration parameter, the iteration number is incremented, and a sequence is repeated, and wherein if it is determined that the iteration is greater than the maximum iteration parameter, then the process terminates, wherein the iteration with the lowest overall distance is selected as the best, and the corresponding assignments of items to clusters, and the cluster scores and parameter estimates are used as the solution.
The method according to the present invention is especially useful in estimating demand model parameters and in decision-support related to price and promotion planning in the retail industry. Obviously, as would be known by one of ordinary skill in the art within the purview of this application, other applications and implementations are possible including clustering financial data where market prices, causal variables and a model form for the relationship is made available, or in the social sciences where quantitatively measurable responses are linked to controllable inputs and a model relating the variables is assumed.
As mentioned above, methods for clustering include hierarchical- and optimization-based techniques, which can be used to cluster retail sales data based on differences in the time series. The present invention allows usage of these methods to cluster data based on price sensitivity in addition to seasonal effects with reference to a given demand model.
As a result, the inventive method can reliably estimate demand model parameters and in decision-support related to price and promotion planning in the retail industry.